﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
#include <ctime>
using namespace std;
// 原题连接：https://www.luogu.com.cn/problem/P2698#submit
/*
题目描述：
农夫约翰一直难以让他种植的植物茁壮成长，他需要你来给植物适当的浇水。

给定二维平面中 N
 个雨滴的位置，其中 y
 表示雨滴的垂直高度，x
 表示其在一维数轴上的位置。

fig_flowerpot.png

每个雨滴以每秒 1
 个单位长度的速率向下（朝 x
 轴）下落。

你需要将宽度为 W
 的农夫约翰的花盆沿 x
 轴放置在某处，以便第一个雨滴击中花盆与最后一个雨滴击中花盆之间的时间差至少为 D
（使得花盆中的花获得充足的水）。

一滴水落在花盆的边缘就等于击中了花盆。

给定 D
 的值和 N
 个雨滴的位置，请计算 W
 的最小可能值。

输入格式
第一行包含两个整数 N
 和 D
。

接下来 N
 行，每行包含两个整数 (x,y)
，表示一个雨滴的位置坐标。

输出格式
输出 W
 的最小可能值。

如果无解，则输出 −1
。

数据范围
1≤N≤105
,
1≤D≤106
,
0≤x,y≤106
输入样例：
4 5
6 3
2 4
4 10
12 15
输出样例：
2
样例解释
将宽度为 2
 的花盆放置在 x=4..6
 处，可以接到雨滴 1
 和 3
，两雨滴接到的时间差为 10−3=7
。
*/


// 开始解题；
// 方法单调队列

// 核心思想：思路类似于：LeetCode 1438. 绝对差不超过限制的最长连续子数组

int main() {
    time_t t1 = time(nullptr);
    int n = 0, limit = 0;
    scanf("%d%d", &n, &limit);
    vector<pair<int, int>> nums(n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &nums[i].first, &nums[i].second);
    }
    // 按照x坐标排序
    sort(nums.begin(), nums.end(), [&](const pair<int, int>& p1, const pair<int, int>& p2) {
        return p1.first < p2.first;
        });
    deque<int> qmin, qmax;
    const int INF = 0x3f3f3f3f;
    int ret = INF;
    for (int left = 0, right = 0; right < n; right++) {
        while (!qmin.empty() && nums[qmin.back()].second > nums[right].second) {
            qmin.pop_back();
        }
        while (!qmax.empty() && nums[qmax.back()].second < nums[right].second) {
            qmax.pop_back();
        }
        qmin.push_back(right);
        qmax.push_back(right);
        while (!qmin.empty() && !qmax.empty() && nums[qmax.front()].second - nums[qmin.front()].second >= limit) {
            ret = min(ret, abs(nums[qmax.front()].first - nums[qmin.front()].first));
            if (qmin.front() <= left) {
                qmin.pop_front();
            }
            if (qmax.front() <= left) {
                qmax.pop_front();
            }
            left++;
        }
    }
    if (ret == INF) {
        ret = -1;
    }
    printf("%d\n", ret);
    time_t t2 = time(nullptr);
    printf("计算时间：%dms\n", t2 - t1);
    return 0;
}